package com.linyaonan.leetcode.medium._105;

import java.util.ArrayList;
import java.util.List;

/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 * <p>
 * 注意:
 * 你可以假设树中没有重复的元素。
 * <p>
 * 例如，给出
 * <p>
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 *
 * @author: Lin
 * @date: 2020/1/18
 */
public class ConstructBinaryTree {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        List<Integer> pre = new ArrayList<>();
        List<Integer> in = new ArrayList<>();
        for (int i : preorder) {
            pre.add(i);
        }
        for (int i : inorder) {
            in.add(i);
        }
        return getTreeNode(pre, in);
    }

    private TreeNode getTreeNode(List<Integer> preorder, List<Integer> inorder) {
        int rootValue = preorder.get(0);
        TreeNode root = new TreeNode(rootValue);
        List<Integer> leftIn = new ArrayList<>();
        List<Integer> rightIn = new ArrayList<>();
        boolean get = false;
        for (int i = 0; i < inorder.size(); i++) {
            int t = inorder.get(i);
            if (t == rootValue) {
                get = true;
                continue;
            }
            if (!get) {
                leftIn.add(t);
            } else {
                rightIn.add(t);
            }
        }
        List<Integer> leftPre;
        List<Integer> rightPre;
        leftPre = preorder.subList(1, leftIn.size() + 1);
        rightPre = preorder.subList(leftIn.size() + 1, inorder.size());
        if (leftPre.size() != 0) {
            root.left = getTreeNode(leftPre, leftIn);
        } else {
            root.left = null;
        }
        if (rightPre.size() != 0) {
            root.right = getTreeNode(rightPre, rightIn);
        } else {
            root.right = null;
        }

        return root;
    }
}
